import math
import random

def assign_cluster(x, centers):
    """
    将样本分配到最近的聚类中心
    x: 单个样本（列表或元组）
    centers: 聚类中心列表（每个元素为样本格式）
    return: 最近聚类中心的索引
    """
    min_dist = float('inf')
    cluster_idx = 0
    for i, c in enumerate(centers):
        # 计算欧氏距离
        dist = math.sqrt(sum([(a - b) **2 for a, b in zip(x, c)]))
        if dist < min_dist:
            min_dist = dist
            cluster_idx = i
    return cluster_idx

def Kmeans(data, k, epsilon=1e-6, iteration=100):
    """
    K均值聚类算法实现
    data: 样本列表（每个样本为可迭代对象）
    k: 聚类数量
    epsilon: 中心变化阈值（小于此值认为收敛）
    iteration: 最大迭代次数
    return: (聚类结果, 最终聚类中心)
    """
    # 检查输入有效性
    if k <= 0 or k > len(data):
        raise ValueError("k值必须为正整数且不大于样本数量")
    if len(data) == 0:
        raise ValueError("数据不能为空")
    
    # 初始化聚类中心（随机选择k个不同样本）
    centers = random.sample(data, k)
    n_features = len(data[0])
    
    for _ in range(iteration):
        # 分配样本到聚类
        clusters = [[] for _ in range(k)]
        for x in data:
            idx = assign_cluster(x, centers)
            clusters[idx].append(x)
        
        # 计算新的聚类中心
        new_centers = []
        for cluster in clusters:
            if not cluster:  # 避免空聚类（随机重置中心）
                new_center = random.choice(data)
            else:
                # 计算每个特征的均值
                new_center = [sum(dim) / len(cluster) for dim in zip(*cluster)]
            new_centers.append(new_center)
        
        # 检查收敛（所有中心变化小于epsilon）
        center_changes = [
            math.sqrt(sum([(a - b)** 2 for a, b in zip(c, nc)]))
            for c, nc in zip(centers, new_centers)
        ]
        if max(center_changes) < epsilon:
            break
        
        centers = new_centers
    
    # 生成最终聚类结果（每个样本对应的聚类索引）
    result = [assign_cluster(x, centers) for x in data]
    return result, centers